package com.bo.day20231212;

import java.util.HashMap;

/**
 * https://leetcode.cn/problems/implement-trie-prefix-tree/description/
 * 图：https://cloud.fynote.com/share/d/NWWMQ7p
 * @Author: gpb
 * @Date: 2023/12/12 11:48
 * @Description:
 */
public class TrieTreeVersion {

    public static class Node {
        private int pass;
        private int end;
        private HashMap<Integer, Node> nexts;

        public Node () {
            // 节点的经过次数记录
            this.pass = 0;
            // 节点的结束次数记录
            this.end = 0;
            // 路线使用用ASCII来计算路线
            // key是ASCII
            nexts = new HashMap<>();
        }
    }

    public static class Trie {
        private Node root;

        public Trie () {
            this.root = new Node();
        }

        /**
         * 添加单词到字典树
         *
         * @param word
         */
        public void insert (String word) {
            if (word == null) {
                return;
            }
            char[] chars = word.toCharArray();
            Node p = root;
            p.pass++;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i];
                if (!p.nexts.containsKey(index)) {
                    p.nexts.put(index, new Node());
                }
                p = p.nexts.get(index);
                p.pass++;
            }
            p.end++;
        }

        public void delete(String word){
            if(!search(word)){
                return;
            }
            char[] chars = word.toCharArray();
            Node p = root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i];
                if (--p.nexts.get(index).pass == 0) {
                    p.nexts.remove(index);
                    return;
                }
                p = p.nexts.get(index);
            }
            p.end--;
        }

        public boolean search (String word) {
            if (word == null) {
                return false;
            }
            char[] chars = word.toCharArray();
            Node p = root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i];
                if (!p.nexts.containsKey(index)) {
                    return false;
                }
                p = p.nexts.get(index);
            }
            return true;
        }

        public boolean startsWith(String prefix) {
            if (prefix == null) {
                return false;
            }
            char[] chars = prefix.toCharArray();
            Node p = root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i];
                if (!p.nexts.containsKey(index)) {
                    return false;
                }
                p = p.nexts.get(index);
            }
            return true;
        }
    }

}
